Same Tree || Symmetric Tree

发表于

Same Tree

Question

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Analysis
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null)
            return true;
        if((p==null&&q!=null)||(p!=null&&q==null)||(p.val!=q.val))
            return false;
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

Symmetric Tree

Question

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

Analysis
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null)
            return true;
        return helper(root.left,root.right);
    }
    
    private boolean helper(TreeNode lt, TreeNode rt){
        if(lt==null&&rt==null)
            return true;
        if((lt==null&&rt!=null)||(lt!=null&&rt==null)||(lt.val!=rt.val))
            return false;
        return helper(lt.left,rt.right)&&helper(lt.right,rt.left);
    }
}